The present invention relates to an improvement in a method for generating random numbers or random sources, in particular sources developed in cryptographic systems such as random number generators on board smart cards.
In particular, it is intended to be implemented in testing and validating electronic devices of the following types: smart cards; Personal Computer Memory Card International Association (PCMCIA) cards; badges; contactless cards, or any other handheld, wearable, or portable device.
Most public-key cryptographic systems (also known as “asymmetric cryptography” systems) and most secret-key cryptographic systems (also known as “symmetric cryptography” systems) require secret random numbers to be drawn. It is essential for such random numbers (which subsequently serve as keys) to be unpredictable a priori, and not to have any regular patterns enabling them to be found by exhaustive or improved exhaustive search strategies in which the most probable keys are looked for first.
It is possible to construct a random source on the basis of a function whose inverse is difficult to compute. Let f be such a function. It is possible to construct a random source by starting by selecting a random initialization variable s, and by applying the function f to the succession of values s, s+1, s+2, . . . The output of the random source is defined as f(s),f(s+1),f(s+2), . . . . As a function of the properties of the function f used, it can be preferable to keep only a few bits of the output f(s),f(s+1),f(s+2). . .
A method for generating random numbers on the basis of a function whose inverse is difficult to compute is specified in ANSI Standard X9.17. That method uses the Data Encryption Standard (DES) algorithm with a secret key K that must be used only in that algorithm. The method for generating random numbers takes as input a random and secret integer s of size 64 bits, and an integer m, and sends back as output m 64-bit random integers x1, x2, . . . , xm. That method is characterized by the following three steps:
1) With the DES algorithm and using the key K, encrypt a value D representing date data and put the result in the integer variable I.
2) For j in the range 1 to m, execute the following steps:
2) a) Replace s by s XOR I. 2) b) Put in xj the result of the encryption of s with the DES algorithm using the key K.
2) c) Replace s with xj XOR I.
2) d) Put in s the result of the encryption of s with the DES algorithm using the secret key K.
3) Return as output the succession (x1, x2, . . . , xm).
It is possible to use this random number generator in an application for which the random number generator is already available, but is deemed to be of insufficient quality, e.g. a random number generator on board the microprocessor of a smart card. In which case, the above-described method is used to improve the quality of the random number generator. That method takes as input a random and secret integer s of size 64 bits and an integer m, and it sends back as output m 64-bit random integers x1, x2, . . . , xm. The method uses the Data Encryption Standard (DES) with a secret key K which must be used only in that algorithm. The method uses a source S of quality deemed to be insufficient of random integers on 64 bits. The method is characterized by the following three steps:
1) For j in the range 1 to m
1) a) Generate an integer I by means of the source S.
1) b) Replace s by s XOR I.
1) c) Put in xj the result of the encryption of s with the DES algorithm using the key K.
1) d) Generating an integer I by means of the source S.
1) e) Replace s with xj XOR I.
1) f) Put in s the result of the encryption s with the DES algorithm using the key K.
2) Return as output the succession (x1, x2, . . . , xm).
It has appeared that implementing a secret-key encryption algorithm (e.g. the DES algorithm) on a smart card is vulnerable to attacks consisting of differential analysis of current consumption or “Differential Power Analysis” (DPA) making it possible to discover the secret key. The principle of such DPA attacks is based on the fact that the power consumption of (i.e. the current consumed by) the microprocessor executing instructions varies depending on the item of data that is being manipulated. To discover the secret key, it is necessary for the input message or the output message of the encryption algorithm to be known.
The two above-described methods of generating random numbers are thus vulnerable to attacks of the DPA type. The random numbers sent back as output by those two methods are output messages from the encryption algorithm. On the basis of the power consumption of the smart card, it is thus possible to discover the encryption key K, and thus then to predict the output of the random number generator.